4.50 Since a binary search tree with N nodes has N + 1 null references, half the space allocated in a binary search tree for link information is wasted. Suppose that if a node has a null left child, we make its left child link to its inorder predecessor, and if a node has a null right child, we make its right child link to its inorder successor.This is known as a threaded tree, and the extra links are called threads. a. How can we distinguish threads from real children links? Sol: You need an extra bit for each thread. c. What is the advantage of using threaded trees? Sol: You can do tree traversals somewhat easier and without recursion. The disadvantage is that it reeks of old-style hacking. | |
| View Solution | |
| << Back | |